{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基于随机游走的 PersonalRank 算法\n",
    "\n",
    "基于上一小节图中顶点相关性的三个因素，我们研究一下一种基于随机游走的 PersonalRank 算法\n",
    "\n",
    "## PersonalRank 公式推导\n",
    "\n",
    "### 算法抽象\n",
    "\n",
    "#### 文字描述\n",
    "\n",
    "假设要给用户 u 进行个性化推荐，可以从用户 u 对应的节点 $v_u$ 开始在用户-物品二分图上随机游走。游走到任意一个节点时，首先按照概率 $\\alpha$ 决定是继续游走，还是停止本次游走并从节点 $v_u$ 重新开始游走。如果继续游走，那么就从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。 这样，经过很多次随机游走后，每个物品节点被访问到的概率会收敛到一个数。最终的推荐列表中物品的权重就是物品节点的访问概率。\n",
    "\n",
    "#### 数学公式\n",
    "\n",
    "$$\\begin{equation}\n",
    "PR(v)=\\left\\{\n",
    "\\begin{aligned}\n",
    "\\alpha \\sum_{\\hat v \\in in(v)} \\frac{PR(\\hat v)}{|out(\\hat v)|} (v \\not = v_A) \\\\\n",
    "(1- \\alpha) + \\alpha \\sum_{\\hat v \\in in(v)} \\frac{PR(\\hat v)}{|out(\\hat v)|} (v = v_A)\n",
    "\\end{aligned}\n",
    "\\right.\n",
    "\\end{equation}$$\n",
    "\n",
    "##### 缺点\n",
    "\n",
    "虽然 PersonalRank 算法有较好的理论解释，但是该算法在时间复杂度上有者明显的缺点。因为在为每个用户进行推荐的时候，都需要在整个用户-物品二分图上进行游走，直到图上每个顶点的PR值收敛。这一过程时间复杂度非常高不仅无法进行实时推荐，甚至离线生成结果也极为耗时。\n",
    "\n",
    "##### 缺点解决方案\n",
    "\n",
    "- 减少迭代次数，在收敛之前就停止迭代。代价是影响精度，但一般来说影响不会特别大。\n",
    "\n",
    "- 从矩阵论出发重新设计算法。\n",
    "\n",
    "#### 矩阵式\n",
    "\n",
    "为解决PersonalRanl全图迭代造成的时间复杂度高的问题，我们可以将运算转为矩阵运算。\n",
    "\n",
    "$$ M_{v\\hat v} = \\frac{1}{|out(i)|} $$\n",
    "\n",
    "$$ r = (1-\\alpha)r_0 + \\alpha M^Tr $$\n",
    "\n",
    "$$ r = (1-\\alpha)(1-\\alpha M^T)^{-1} r_0 $$\n",
    "\n",
    "也有表示成以下形式的\n",
    "\n",
    "$$ r = (1-\\alpha) r_0 + \\alpha M^Tr $$\n",
    "\n",
    "$$ M_{ij} = \\frac{1}{out(i)}j \\in out(i) else 0 $$\n",
    "\n",
    "$$ (E - \\alpha M^T) * r = (1 - \\alpha) r_0 $$\n",
    "\n",
    "$$ r = (E - \\alpha M^T)^{-1} (1 - \\alpha) r_0 $$\n",
    "\n",
    "因此只需要计算一次 $(1-\\alpha M^T)^{-1}$，这里的 $1-\\alpha M^T$ 是稀疏矩阵。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
